package com.zk.algorithm.array;

import com.zk.algorithm.annotation.Easy;
import com.zk.algorithm.annotation.LeetCodeExplore;

import java.util.Arrays;
import java.util.HashMap;

/**
 * You may assume that each input would have exactly one solution, and you may not use the same element twice.
 *
 * @author zk
 */
@LeetCodeExplore
@Easy
public class TwoSum {

    /**
     * 使用一个 HashMap 保存下标
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer /** 数字 **/, Integer/** 数字的索引 **/> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{ map.get(target - nums[i]).intValue(), i };
            }

            map.put(nums[i], i);
        }

        return new int[]{ 0, 0 };
    }

    /**
     * 错误的解法，Arrays.sort 会破坏下标
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSumWrong(int[] nums, int target) {
        Arrays.sort(nums);

        int i = 0;
        int j = nums.length - 1;

        while (i < j) {
            int sum = nums[i] + nums[j];

            if (sum == target) {
                return new int[]{ i, j };
            } else if (sum < target) {
                i++;
            } else if (sum > target) {
                j--;
            }

        }

        return new int[0];
    }

}
